/**
 * 62. Unique Paths 不同路径
 * https://leetcode-cn.com/problems/unique-paths/
 */
class UniquePaths {

    /**
     * 方法：使用动态规划计算从起点到终点的唯一路径数
     *      使用一维数组f[j]表示到达第i行第j列的路径数
     *      状态转移方程：f[j] = f[j] + f[j-1]
     *      其中f[j]表示从上方来的路径数，f[j-1]表示从左方来的路径数
     *
     * Args:
     *      m: int - 网格的行数
     *      n: int - 网格的列数
     *
     * Returns:
     *      int: 从左上角到右下角的唯一路径数
     *
     * Time: O(m*n) - 需要遍历整个m*n的网格
     *
     * Space: O(n) - 使用长度为n的一维数组存储状态
     */
    public int uniquePaths(int m, int n) {
        int f[] = new int[n+1];
        f[1] = 1;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                f[j+1] += f[j];
            }
        }
        return f[n];
    }

    /**
     * 方法：使用组合数学公式计算从起点到终点的唯一路径数
     *      从m+n-2步中选择m-1步向下移动的组合数
     *      使用组合数公式C(n,k) = n!/(k!(n-k)!)
     *
     * Args:
     *      m: int - 网格的行数
     *      n: int - 网格的列数
     *
     * Returns:
     *      int: 从左上角到右下角的唯一路径数
     *
     * Time: O(min(m,n)) - 计算组合数时循环min(m,n)次
     *
     * Space: O(1) - 只使用常数额外空间
     */
    public int uniquePaths1(int m, int n) {
        //组合数公式：从（m+n-2）中选择（m-1）中向下的方式
        //公式：n!/k!(n-k)!  其中 n = (m+n-2) k = m-1
        //推导后得出：（m+n-2)! = (m+n-2)!/(m-1)!(m+n-2-(m-1))! 
        //                   = (m+n-1)!/(m-1)!(n-1)!
        return (int)comb(m+n-2, m-1); 
    }

    private long comb(int n, int k){
        k = Math.min(k, n-k);
        long res = 1;
        //(n k) = (n * (n-1) * ... * (n+1-k))/1*2*...*k
        for(int i = 1; i<=k; i++){
            res = res*(n+1-i)/i;
        }
        return res;
    }
}